#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "SqQueue.h"
#define MaxVertNum 10

typedef struct{
    //顶点数和边数
    int vertNum, edgeNum;
    //邻接矩阵表边是否存在
    int edges[MaxVertNum][MaxVertNum];
    //顶点的名称
    char verts[MaxVertNum][100];
}AMGraph;

//根据顶点名称查找在图邻接矩阵中的行（列）号
int findVertIndex(AMGraph G, char *vert){
    for(int i = 0; i < G.vertNum; i++){
        if(strcmp(G.verts[i], vert) == 0)
            return i;
    }
    return -1;
}

//建立有向图
void createDAMGraph(AMGraph &G){
    printf("-----输入顶点个数、边的个数：-----\n");
    scanf("%d %d", &G.vertNum, &G.edgeNum);
    //初始化邻接矩阵
    int i, j;
    for(i = 0; i < G.vertNum; i++){
        for(j = 0; j < G.vertNum; j++){
            G.edges[i][j] = 0;
        }
    }
    //输入顶点的信息
    printf("-----输入顶点信息:-----\n");
    for(i = 0; i < G.vertNum; i++)
        scanf("%s", G.verts[i]);

    //输入边
    int l, r;
    printf("-----输入边:-----\n");
    char a[100], b[100];
    for(i = 0; i < G.edgeNum; i++){
        printf("输入边的两个顶点名称："); 
        scanf("%s %s", a, b);
        l = findVertIndex(G, a);
        r = findVertIndex(G, b);
        G.edges[l][r] = 1;
    }
}
void printMatrix(int matrix[][MaxVertNum], int n);
void BFS(AMGraph G){
    int visted[G.vertNum] = {0};
    SqQueue Q;
    init(Q);
    printf("邻接矩阵：\n");
    printMatrix(G.edges, G.vertNum);
    printf("\n");
    for(int i = 0; i < G.vertNum; i++){
        if(!visted[i]){
            //访问
            printf("%s", G.verts[i]);
            visted[i] = 1;
            //入队
            enter(Q, i);
            while(!isEmpty(Q)){
                int index;
                remove(Q, index);
                for(int j = 0; j < G.vertNum; j++){
                    if(G.edges[index][j] && !visted[j]){
                        //访问
                        printf("%s", G.verts[j]);
                        visted[j] = 1;
                        //入队
                        enter(Q, j);
                    }
                }
            }
        }
    }
}
void printMatrix(int matrix[][MaxVertNum], int n){
    int i, j;
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            printf("%d\t", matrix[i][j]);
        }
        printf("\n");
    }
}
// int visted[MaxVertNum] = {0};
// void dfs(AMGraph G, int i){
//     printf("%s", G.verts[i]);
//     visted[i] = 1;
//     for(int j = 0; j < G.vertNum; j++){
//         if(j == i)
//             continue;
//         if(G.edges[i][j] && !visted[j])
//             dfs(G, j);
//     }
// }
// void DFS(AMGraph G){
//     for(int i = 0; i < MaxVertNum; i++) visted[i] = 0;

//     for(int i = 0; i < G.vertNum; i++){
//         if(!visted[i])
//             dfs(G, i);
//     }
// }





